package interviewpreparationkit.sorting

/**
 * [Merge Sort: Counting Inversions](https://www.hackerrank.com/challenges/ctci-merge-sort)
 */
// Complete the countInversions function below.
fun countInversions(arr: Array<Int>): Long {
    var swaps = 0L
    val temp = Array(arr.size) { 0 }
    fun merge(arr1: Array<Int>, begin: Int, mid: Int, end: Int) {
        var i = begin
        var j = mid
        var k = 0

        while (i < mid && j < end) {
            temp[k++] = if (arr1[i] <= arr1[j]) {
                arr1[i++]
            } else {
                swaps += (mid - i)
                arr1[j++]
            }
        }
        while (i < mid) {
            temp[k++] = arr1[i++]
        }
        while (j < end) {
            temp[k++] = arr1[j++]
        }
        i = begin
        k = 0
        while (i < end) {
            arr1[i++] = temp[k++]
        }
    }

    fun mergeSort(arr1: Array<Int>, begin: Int, end: Int) {
        if (end - begin < 2) return
        val mid = (begin + end) / 2
        mergeSort(arr1, begin, mid)
        mergeSort(arr1, mid, end)
        merge(arr1, begin, mid, end)
    }

    mergeSort(arr, 0, arr.size)
    return swaps
}